/* PROBLEME N° 10
 * Trouver la somme de tous les nombres premiers
 * inférieurs à 2000000
 *
 * Date de résolution : 15 Janvier 2010 à 00 : 40
 * Réponse : 142913828922
 * Pour 10000000, çà donne 3203324994356 en 0m6.223s
 * Pour 100000000, on a 279209790387276 en 3m30.988s
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int premier(int);

int main(int argc, char *argv[])
{
    long long somme = 5;
    long n = 2000000;
    int i = 5;
    
    while(i <= n)
    {
        if(premier(i))
            somme += i;
        i += 2;
        if((i <= n) && premier(i))
            somme += i;
        i += 4;
    }

    printf("%lld\n", somme);

    return 0;
}

int premier(int n)
{
    int i = 0, limite = 0;

    if(n == 1)
        return 0;
    else if(n < 4) // 2 et 3 sont des nombres premiers
        return 1;
    else if(n % 2 == 0)
        return 0;
    else if(n < 9) // 4, 6, et 8 ont été exclus par la condition précédente
        return 1;
    else if(n % 3 == 0)
        return 0;
    else
    {
        limite = (int)sqrt(n);
        i = 5;
        while(i <= limite)
        {
            if(n % i == 0)
                return 0;
            if(n % (i + 2) == 0)
                return 0;
            i += 6;
        }
        return 1;
    }
}

    
    
